/**
 * 问题描述：有n个男生和女生去食堂吃饭，假设食堂目前没有零钱找补，只能通过男女生打完饭后
 * 所获得的钱去找补，每个女生都是带着5元去打饭，而男生则是带着10元，一份套餐的价格是5元，
 * 请问有多少种合理的安排顺序
 */

package com.faiz.algorithm;

public class Dining {
    /*************************************************/
    public static int Ctl(int i, int j) {
        if (1 == i && 1 == j) {
            return (1);
        }
        if (i < j && i > 1 && j > 1) {
            return (Ctl(i - 1, j) + Ctl(i, j - 1));
        }
        if (i == j) {
            return (Ctl(i - 1, j));

        }
        if (i == 1) {
            return (Ctl(i, j - 1));
        }

        return (0);
    }

    //其中j的数量表示女生，i的数量表示男生
    public static int Ct2(int i, int j, int[][] array) {
        if (0 == i && 0 == j) {
            return 1;
        }
        array[0][0] = 1;
        for (int jIndex = 1; jIndex < j; jIndex++) {
            for (int iIndex = 0; iIndex <= jIndex; iIndex++) {
                if (0 == iIndex) {
                    array[jIndex][iIndex] = array[jIndex - 1][iIndex];
                }
                if (iIndex == jIndex) {
                    array[jIndex][iIndex] = array[jIndex][iIndex - 1];
                }
                if (iIndex < jIndex && iIndex != 0) {
                    array[jIndex][iIndex] = array[jIndex - 1][iIndex] + array[jIndex][iIndex-1];
                }
            }
        }

        return array[j - 1][i - 1];
    }


}
